package com.hardy.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

/**
 * The set[1,2,3,…,n]contains a total of n! unique permutations. By listing and labeling all of the
 * permutations in order, We get the following sequence (ie, for n = 3): "123" "132" "213" "231"
 * "312" "321"
 *
 * Given n and k, return the k th permutation sequence. Created by 1340760685@qq.com on 2016/9/27.
 */
public class PermutationSequence {
    public static String getPermutation(int n, int k) {
        int[] A = new int[n];
        for (int i = 0; i < n; i++) {
            A[i] = i + 1;
        }
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        pailie(A, res, 0);
        Collections.sort(res, new Comparator<ArrayList<Integer>>() {
            @Override
            public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {
                for (int i = 0; i < o1.size(); i++) {
                    if (o1.get(i) != o2.get(i)) {
                        if (o1.get(i) > o2.get(i)) {
                            return 1;
                        } else {
                            return -1;
                        }
                    }

                }
                return 0;
            }
        });
        ArrayList<Integer> result = res.get(k - 1);
        StringBuilder sb = new StringBuilder();
        for (Integer i : result) {
            sb.append(i);
        }
        return sb.toString();
    }

    private static void pailie(int[] A, ArrayList<ArrayList<Integer>> res, int begin) {
        if (begin >= A.length) {
            ArrayList<Integer> arr = new ArrayList<>();
            for (int i = 0; i < A.length; i++) {
                arr.add(A[i]);
            }
            res.add(arr);
        } else {
            for (int i = begin; i < A.length; i++) {
                swap(A, begin, i);
                pailie(A, res, begin + 1);
                swap(A, i, begin);
            }
        }
    }

    private static void swap(int[] a, int begin, int i) {
        int temp = a[begin];
        a[begin] = a[i];
        a[i] = temp;
    }

    public static String _getPermutation(int n,int k){
        int[] A=new int[n];
        for(int i=0;i<n;i++){
            A[i]=i+1;
        }
        boolean[] flag=new boolean[n+1];
        ArrayList<ArrayList<Integer>> res=new ArrayList<>();
        ArrayList<Integer> arr=new ArrayList<>();
        dfs(A,res,0,flag,arr);
        ArrayList<Integer> result = res.get(k - 1);
        StringBuilder sb = new StringBuilder();
        for (Integer i : result) {
            sb.append(i);
        }
        return sb.toString();
    }

    private static void dfs(int[] A, ArrayList<ArrayList<Integer>> res, int start, boolean[] flag,ArrayList<Integer> arr) {
        if(start>=A.length){
            res.add(new ArrayList<>(arr));
        }else{
            for(int i=1;i<=A.length;i++){
                if(!flag[i]){
                    flag[i]=true;
                    arr.add(i);
                    dfs(A,res,start+1,flag,arr);
                    flag[i]=false;
                    arr.remove(arr.size()-1);
                }
            }
        }
    }
    public static String __getPermutation(int n,int k){
        StringBuilder sb=new StringBuilder();
        StringBuilder res=new StringBuilder();
        for(int i=1;i<=n;i++){
            sb.append(i);
        }
        int[] fb=new int[n];
        fb[0]=1;
        for(int i=1;i<n;i++){
            fb[i]=fb[i-1]*i;
        }
        k--;
        for(int i=n-1;i>=0;i--){
            int code=k/fb[i];
            res.append(sb.charAt(code)+" ");
            sb.deleteCharAt(code);
            k=k%fb[i];
        }
        return res.toString();
    }
    public static void main(String[] args) {
        /*long start=System.currentTimeMillis();
        String str = getPermutation(19,171669);
        long end=System.currentTimeMillis();
        String _str=_getPermutation(19,171669);
        System.out.println(_str);*/
        long _end=System.currentTimeMillis();
        String str1=__getPermutation(10,171669);
        long end1=System.currentTimeMillis();
        /*System.out.println(end-start);
        System.out.println(_end-end);*/
        System.out.println(end1-_end);
        System.out.println(str1);
    }

}
